package org.ala.tiktools.tools.queue;

import java.util.Arrays;

/**
 *	循环数组实现的队列，固定容量不扩容	
 *
 *	@author ala
 *	@date 2025年4月26日
 */
public class FixedCircularQueue<E> implements IQueue<E> {

	
	/**
	 * 	数据对象
	 */
	protected E[] datas;
	/**
	 * 	指向下一个可写入的位置
	 */
	protected int posLeft = 0, posRight = 1;
	protected int size, capacity;
	protected QueueIterator iterator;
	
	public FixedCircularQueue(E[] arr) {
		this(arr, true);
	}
	public FixedCircularQueue(E[] arr, int pl, int pr) {
		this(arr, pl, pr, true);
	}
	public FixedCircularQueue(E[] arr, boolean clearObject) {
		datas = arr;
		capacity = arr.length;
		posLeft = 0;
		posRight = 1;
		size = 0;
		iterator = new QueueIterator();
	}
	public FixedCircularQueue(E[] arr, int pl, int pr, boolean clearObject) {
		datas = arr;
		capacity = arr.length;
		posLeft = pl;
		posRight = pr;
		size = pr > pl ? pr - pl - 1 : pr + capacity-pl-1;
		iterator = new QueueIterator();
	}
	

	@Override
	public boolean isEmpty() {
		return size == 0;
	}
	@Override
	public int size() {
		return size;
	}

	
	@Override
	public boolean addFirst(E e) {
		if (size == capacity) {return false;}
		datas[posLeft--] = e;
		if (posLeft == -1) {posLeft = capacity-1;}
		size++;
		return true;
	}
	@Override
	public E removeFirst() {
		if (size == 0) {return null;}
		if (++posLeft == capacity) {posLeft = 0;}
		E v = datas[posLeft];
		datas[posLeft] = null;
		return v;
	}
	@Override
	public E first() {
		if (size == 0) { return null; }
		int p = posLeft+1;
		if (p == capacity) {p = 0;}
		return datas[p];
	}

	
	@Override
	public boolean addLast(E e) {
		if (size == capacity) {return false;}
		datas[posRight++] = e;
		if (posRight == capacity) {posRight = 0;}
		size++;
		return true;
	}
	@Override
	public E removeLast() {
		if (size == 0) {return null;}
		if (--posRight == -1) {posRight = capacity - 1;}
		E v = datas[posRight];
		datas[posRight] = null;
		return v;
	}
	@Override
	public E last() {
		if (size == 0) {return null;}
		int p = posRight-1;
		if (p == -1) {p = capacity - 1;}
		return datas[p];
	}
	
	
	@Override
	public IQueueIterator<E> firstIterator() {
		iterator.resetFirst();
		return iterator;
	}
	@Override
	public IQueueIterator<E> lastIterator() {
		iterator.resetLast();
		return iterator;
	}
	
	/**
	 * 	删除p位，左边右移
	 * 	<p>	还有优化的空间，在性能极度敏感的地方，%运算也“很吃”cpu
	 * 	@return	-1：队列本来就是空，无法删除<br/>
	 * 			-2：p不在合法范围内<br/>
	 * 			 0：异常情况，没有执行（预留黑天鹅，目前代码里没有返回0的地方）<br/>
	 * 			 1：队列往左删除<br/>
	 * 			 2：队列往右删除<br/>
	 */
	public int remove(int p) {
		if (size == 0) {return -1;}
		//	验证p的合法性，只能在可读区域remove
		if (posLeft == posRight && posLeft == p) { return -2; }
		if (posLeft < posRight && (p <= posLeft || p >= posRight)) { return -2; }
		if (posLeft > posRight && (p >= posLeft && p <= posRight)) { return -2; }
		//	转换为逻辑下标，r永远在l右边，p永远在[l,r]之间
		int l = posLeft, r = posRight + ((posRight < posLeft) ? capacity : 0);
		p = p + (p < posLeft ? capacity : 0);
		int dl = p - l, dr = r - p;
		//	离左边更近
		if (dl < dr) {
			for (int i = p ; i > l+1 ; i--) {
				System.out.println("FixedArray remove");
				
				int a = i % capacity, b = (i-1 + capacity) % capacity;
				swap(a, b);
			}
			if (++posLeft == capacity) {posLeft = 0;}
			datas[posLeft] = null;
			size--;
			return 1;
		}
		//	离右边更近
		else {
			for (int i = p ; i < r-1 ; i++) {
				System.out.println("FixedArray remove");
				
				int a = i % capacity, b = (i+1) % capacity;
				swap(a, b);
			}
			if (--posRight == -1) {posRight = capacity-1;}
			datas[posRight] = null;
			size--;
			return 2;
		}
	}
	
	
	/**
	 * 在p位置插入元素
	 * <p>	还有优化空间，在性能极度敏感的地方，%运算也“很吃”cpu
	 * @return	-1：队列已满<br/>
	 * 			-2：p不在合法位置<br/>
	 * 			 0：异常情况，没有执行（预留黑天鹅，目前代码里没有返回0的地方）<br/>
	 * 			 1：原[left, p]位置左移<br/>
	 * 			 2：原[p, right]位置右移<br/>
	 */
	public int insert(int p, E e) {
		if (size == capacity) { return -1; }
		//	校验p的合法性
		if (posLeft == posRight && p == posLeft) {return -2;}
		if (posLeft < posRight && (p <= posLeft || p >= posRight)) {return -2;}
		if (posRight < posLeft && (p >= posRight && p <= posLeft)) {return -2;}
		//	转换为逻辑下标，r永远在l右边，p永远在[l,r]之间
		int l = posLeft, r = posRight + ((posRight < posLeft) ? capacity : 0);
		p = p + (p < posLeft ? capacity : 0);
		int dl = p - l, dr = r - p;
		//	如果离左边更近
		if (dl < dr) {
			for (int i = l ; i < p ; i++) {
				System.out.println("FixedArray insert");
				
				int a = i % capacity, b = (i+1) % capacity;
				swap(a, b);
			}
			if (--posLeft == -1) {posLeft = 0;}
			datas[p % capacity] = e;
			size++;
			return 1;
		}
		//	如果离右边更近
		else {
			for (int i = r ; i > p ; i--) {
				System.out.println("FixedArray insert");
				
				int a = i % capacity, b = (i-1 + capacity) % capacity;
				swap(a, b);
			}
			if (++posRight == capacity) {posRight = 0;}
			datas[p % capacity] = e;
			size++;
			return 2;
		}
	}
	
	
	protected void swap(int i, int j) {
		E e = datas[i];
		datas[i] = datas[j];
		datas[j] = e;
	}
	
	
	/**
	 * 	全部清空助消化
	 */
	@Override
	public void clear() {
		int l = posLeft, r = posRight;
		if (l >= r) { r += capacity; }
		for (int i = l ; i < r ; i++) {
			int p = i % capacity;
			datas[p] = null;
		}
		posLeft = 0; posRight = 1;
		size = 0;
	}


	/**
	 * 	迭代器
	 */
	public class QueueIterator implements IQueueIterator<E> {
		protected int posOffset = -1;
		protected int size = -1;

		@Override
		public E current() {
			if (posOffset == size) {return null;}
			int p = (posLeft+1 + posOffset) % capacity;
			return datas[p];
		}
		@Override
		public boolean insert(E e) {
			int p = (posLeft + posOffset) % capacity;
			int r = FixedCircularQueue.this.insert(p, e);
			if (r <= 0) {return false;}
			return true;
		}
		@Override
		public void clear() {
			posOffset = -1;
			posOffset = -1;
		}
		
		
		/*************************************************************************************************************
		 * 	从前往后遍历
		 *************************************************************************************************************/
		@Override
		public void resetFirst() {
			size = FixedCircularQueue.this.size;
			posOffset = 0;			
		}
		@Override
		public boolean hasNext() {
			return posOffset < size;
		}
		@Override
		public E next() {
			if (posOffset == size) {return null;}
			int p = (posLeft+1 + posOffset) % capacity;
			E v = datas[p];
			posOffset++;
			return v;
		}
		
		@Override
		public E removeAndNext() {
			int p = (posLeft+1 + posOffset) % capacity;
			E e = datas[p];
			int r = FixedCircularQueue.this.remove(p);
			if (r > 0) {
				size--;
			}
			return e;
		}


		/*************************************************************************************************************
		 * 	从后往前遍历
		 *************************************************************************************************************/
		@Override
		public void resetLast() {
			size = FixedCircularQueue.this.size;
			//	此时的偏移是相对posLeft的偏移
			posOffset = 0;	
		}
		@Override
		public boolean hasPrev() {
			return posOffset < size;
		}
		@Override
		public E prev() {
			if (posOffset == size) {return null;}
			int p = (posRight-1 - posOffset) % capacity;
			E v = datas[p];
			posOffset++;
			return v;
		}
		@Override
		public E removeAndPrev() {
			int p = (posRight-1 - posOffset) % capacity;
			E e = datas[p];
			int r = FixedCircularQueue.this.remove(p);
			if (r > 0) {
				size--;
			}
			return e;
		}
	}
	
	
	/**
	 * 
	 */
	public String toString() {
		StringBuilder sbuf = new StringBuilder();
		sbuf.append("{type:Array, size:").append(size).append(", datas:").append(Arrays.toString(datas)).append(", posLeft:").append(posLeft).append(", posRight:").append(posRight).append("}");
		return sbuf.toString();
	}
	
}
